package arithmetic3.sort;

import java.util.Arrays;

/**
 * @author 姚凤桥
 * @Date 2021/12/15 9:52
 * @Description: 归并排序
 */
public class MergerSort {
    public static void main(String[] args) {
        int arr[] = {6, 1, 68, 3, 9, 32};
        int temp[] = new int[arr.length];
        partition(arr, 0, arr.length - 1, temp);
        System.out.println(Arrays.toString(arr));
    }

    public static void partition(int[] arr, int start, int end, int[] temp) {
        if (start < end) {
            int mid = (start + end) >> 1;

            //将数组向左右两边分解
            partition(arr, start, mid, temp);
            partition(arr, mid + 1, end, temp);

            //合并左右两个数组
            merger(arr, start, mid, end, temp);
        }
    }

    public static void merger(int[] arr, int start, int mid, int end, int[] temp) {
        int i = start;
        int j = mid + 1;
        int t = start;
        //将两个数组中比较小的数开始放入到temp中，直到有一个数组放完
        while (i <= mid && j <= end) {
            if (arr[i] <= arr[j]) {
                //将左边数组小的数放入到temp中
                temp[t++] = arr[i++];
            } else {
                //将右边数组小的数放入到temp中
                temp[t++] = arr[j++];
            }
        }

        //如果左边数组还有没有放完的元素就将他们依次放入到temp中
        while (i <= mid) {
            temp[t++] = arr[i++];
        }

        //如果右边数组还有没有放完的元素就将他们依次放入到temp中
        while (j <= end) {
            temp[t++] = arr[j++];
        }

        //将temp中的元素复制到arr中的对应位置
        while (start <= end) {
            arr[start] = temp[start++];
        }
    }
}
